Part 37: Holman Dynamics

Part 37 - Holman Dynamics

=== Trash World Inbox ===

Last time, I fixed my eye with some hacks, getting high scores of 334, 29, and 10.

silentsnack has both a cycle and lines of code improvement.

The code that gets the EXAs everywhere is quite simple, from the virtual cortex, just repeatedly REPL in the -3 direction, then go to -1 and from there read the nerves, going along the 1 direction so those 3 EXAs can hit them all. Once the edges are reached they'll just die.

There's some clever mathematics tricks though. The DIVI directly returns 0 or 1 based on the #NERV value. The first M call from the cortex EXA subtracts 15 (which is 75 / 5) so that's another two steps in a single cycle.

For this fast solution, the LOOP loop for each of the 3 reader EXAs handles the messages from the lower row, while the SWEEP code adds the values of two nerves together, massages them into a format that is directly usable by the writer EXA and sends that over M. The code seems obvious when you see it but that doesn't mean it's easy to come up with it yourself.


=== Holman Dynamics - Sales System ===

Hopefully this is the last time you'll have to hack yourself like this.



Three votes for "I hope so", one for each of the other options.

I hope so.

Maybe you'll come upon a solution to that.
Some way to keep from having to physically go in and fix yourself every so often...
I wonder what that would entail.
Something to think about.

I met with Ghast, and Ember gave me a new assignment.



Ah, and that happened too, I suppose.



The dataphones were cute, but I still need more computing power.
We need to get me some significant hardware upgrades.



Everyone voted for the same option here.

I assume you have some kind of plan.

Of course.
We're going to buy a supercomputer.
With credit cards.
Specifically, credit cards that were used to buy supercomputers before.
It'll be less suspicious that way.
Someone who buys one supercomputer maybe buys two. Right?
Seems plausible to me.

If you say so...


OST: Network Exploration

The assignment:
- Create a file in your host containing the contiguous 16-value sequence from the garbage file (file 199) that is a valid credit card number. There will be exactly one such sequence.
- For more information see "How to Validate Credit Card Numbers" in the second issue of the zine.

This assignment allows for a max size of 150 lines of code. That's quite high, so this one might get complicated.

I opened up some random files for the screenshot. Other than the garbage file, there are "leads" (e.g. file 224, according to the host name), "accounts" (file 201), and "receipts" (e.g. 262). But all we need is the garbage file. Let's check the zine.



Summarized, to validate a 16-digit number, sum all digits in a particular way. Take the digits in even positions as-is, for the odd ones double the value and if it's 10 or higher, subtract 10. Sum them up and if the result mod 10 equals zero, the number is valid.

This is actually the real-life Luhn algorithm aka mod 10 algorithm, which is used to validate credit card numbers and lots of other id numbers in real life. Wikipedia's description of the algorithm is slightly different but the maths work out to be identical. I think this is a cool touch - and why invent your own algorithm if the real one works perfectly well for a puzzle.



Looking at the file in more detail, those -9999 values help a lot. If there's less than 16 digits before a -9999 I know it will be invalid. What I can't tell yet is if would be faster to just start the algorithm and reset once we hit a -9999, or do a seperate initial pass so we know what values to skip and don't even run the algorithm on that.

There's another potential complication - if there's more than 16 digits in a row, that might mean any window of 16 might be the number. We'll cross that bridge when we get to it.

It is difficult for this EXA to calculate the complete algorithm AND know when to give up because it hit a -9999. I need a place to store the accumulated value, an intermediate register to handle the two steps for the odd digits, a register to count up 16 digits, and one to test if I got a -9999. That's at least 4 registers.

I could copy the whole file to another EXA and have it do logic but all the M calls would be slow. So if XA can do at least some intermediate work before invoking M, that would help.

After some trial and error I settled for this code in XA:
After getting to the garbage file, it starts counting valid values, resetting if it finds an invalid -9999. If it finds 16 valid values it starts sending all of them over M. Then, because there might be more than 16 valid values it will keep sending them until it encounters -9999. In that case, it will actually send -9999 to let the other EXA know it's going to start with a fresh list, and then it will reset to the counter loop.

Now, XB has to do the actual work.

It starts with some setup. The EXA may need to jump back to RETRY later, and in that case it wipes the file its holding (which will contain an invalid number) and create a new one. To save some annoying and slow jumps later, I MAKE an empty file at the start so the WIPE can go right into the loop without crashing the EXA at the start.

I then put in a 0 in the file and copy the 16 values from XA.

The next step is the validation algorithm.
I am using T as my accumulator, so I make sure it's zero at the start. The EXA SEEKs to the start of the file and deletes that 0 I put there, you will see why later.

Then I repeat the same couple of lines 8 times, each repetition handles two digits. For the first (odd) digit, I multiply it by 2, do modulo 9 to remove a 9 if it's greater than that, and add it to T. The even digit can just be added directly. Finally, the modulo 10 check puts a 0 in T only if the number is valid. If the number is found, the program will jump to GOTIT.

I'll show that branch first.
If the number is valid, all I have to do is drop the file and go kill XA which might be trying to send the next digit. LINKing there to kill isn't very pretty but this puzzle is complex enough that I want to see something working first.

So how about if the credit card wasn't valid? Falling through from FJMP GOTIT:
If the next value from XA is -9999 it wants to send a new series. In that case everything in the file is garbage, jump to RETRY and start over. Otherwise, put that value at the end of F and run VALIDATE again. You see what happens here? Since VALIDATE starts by removing the first digit, I actually slid the 16-digit window one digit to the right, and there's a new potentially valid 16-digit number in the file. That's also why I needed to add the 0 there in a new file, to make sure all VALIDATE calls including the first one work.


Is this it? No, not quite.
There is one edge case in which this solution fails.

If an odd digit is exactly 9, it will be doubled to become 18, and 18 mod 9 equals 0, while the validation algorithm needs to get a 9 there. So, sadly, I can't use this particular MODI trick.

A possible solution could be to add a specific X = 9 check, and a code branch that deals with that case. But since I'm already using both X and T, that would require some very awkward shuffling of values. I need something smarter.

And for that, I actually looked at the original description of the Luhn algorithm. It says, if you double a digit, just add the resulting digits together. For instance 6 * 2 = 12, result is 1 + 2 = 3. Starting from any single digit value, the result of this operation is identical to just subtracting 9 from the doubled value.

I just have to implement this efficiently. Is there a combination of operations, using my limited storage space, to do that?

The new code for digits in odd places. I multiply the value again. Then I add that mod 10 to T. That just means adding the ones digit.
I then SEEK back to the original value in the file, and do a DIVI F 5 X. If F is less than 5 this will return 0. If it's between 5 and 9 inclusive, it will return a 1. In other words, it will return the value in the tens place of the doubled digit. Add that to T as well and that's the edge case covered.



Here is the full code.



It runs at 3704/130/7, with top percentiles sitting at 1752, 42, 3.

Before I do anything else, a tiny speed improvement that drops the solution to 3699, without changing the LoC.

Instead of writing a 0 to F at the start, I can put a SEEK -9999 just before the VALIDATE mark, and put another one just above the JUMP VALIDATE, together with a VOID F there.

With that out of the way, getting the activity down to 3 should be easy enough.

3724/136/3.
XB's LINKs are gone. XA tests if XB is sending something after each SENDREMAINING loop, and XB sends a message when it's done. XB does need to test if XA is sending something, because it is possible XA reached the end of the file and died already.

I think the simplest way to reduce the size is by rolling up those loops.

4567/60/7

The 16 iterations read and send loops just keep counters now. The validation loop uses an EOF to check when it's done. To do that test I did have to move the accumulator to X.

I also changed the -9999 so it'd be tested directly against F. That allowed me to remove one of the COPY 0 X lines.

As for reducing the cycle count, obviously from the top percentile, there are large improvements possible. One thing I tried is combining the 16 M sends with SWIZ operations. That doesn't really help because the true bottleneck here is that one EXA completely pauses waiting for the other when they're validating or trying to find credit card numbers. There are certainly ways to parallelize that, but since the basic solution was complex enough as it was, I'll leave that, together with further LoC optimizations, as an exercise to the reader.

It turns out you can order and take delivery of a supercomputer surprisingly fast.
Now I have to figure out how to make use of this thing...
It works in an extremely different way than I'm used to.
I feel like I'm trying to maneuver a big rig after years of being used to a roadster.
That's a use of metaphor. What do you think?



I think it's time for the first vote.

It's the final hacker battle...
Are you excited?
Are you nervous?



Hey, no spoilers, please, Ember. Anyway, the second vote.